import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class SearchGrid
{
	private static int width, height, flooding, waterproof, growth;
	private int nLambdas, water, turnsUnderwater, razors, counter;
	private char[][] grid;
	private Location robo;
	private static Location[] trampolines; //trampolines[0] corresponds to the Location of trampoline A, etc
	private static Location[] trampolineTargets; //trampolineTargets[0] corresponds to the Location that trampoline A is targetted at, etc
	private List<Location> updatableCells;
	//zobrist
	/*
	 * compute bitstrings for
	 * every non wall square: R * \ W @ (+5 states for each square)
	 * every square that has: . A-I 1-9 ! (+1 state for each square)
	 * liftopen
	 * every possible flood height (0 - height)
	 * every possible turnsUnderwater value (0 - waterproof+1)
	 */
	private long hashCode;
	private static long[][][] GRIDSTRINGS;
	private final static int ROBOT = 0, ROCK = 1, LAMBDA = 2, BEARD = 3, HOROCK = 4, STATIC = 5;
	private static long OPENSTRING;
	private static long[] WATERSTRINGS, UNDERWATERSTRINGS;

	public SearchGrid(String[] raw)
	{
		width = 0;
		height = raw.length;
		for (int i = 0; i < raw.length; i++) // metadata check
		{
			int length = raw[i].length();
			width = Math.max(width, length);
			if (length == 0) // newline, indicative of metadata
			{
				height = i;
				break;
			}
		}

		grid = new char[width][height];
		nLambdas = 0;
		updatableCells = new ArrayList<Location>();
		trampolines = new Location[9];
		Map<Character, Location> targets = new HashMap<Character, Location>();
		hashCode = 0;
		GRIDSTRINGS = new long[width][height][];
		Random random = new SecureRandom();
		for (int y = 0; y < height; y++)
		{
			String row = raw[height - 1 - y]; // reversed
			for (int x = 0; x < row.length(); x++) // may NOT be the same as width due to nonrectangular grids
			{
				char current = row.charAt(x);
				grid[x][y] = current;
				if(current != '#')
				{
					long[] zobrist = new long[]{ random.nextLong(), random.nextLong(), random.nextLong(), random.nextLong(), random.nextLong() };
					switch (current)
					{
					case 'R':
						robo = new Location(x, y);
						hashCode ^= zobrist[ROBOT];
						break;
					case '*':
						hashCode ^= zobrist[ROCK]; break;
					case '\\':
						nLambdas++;
						hashCode ^= zobrist[LAMBDA]; break;
					case 'W':
						hashCode ^= zobrist[BEARD]; break;
					case '@':
						nLambdas++;
						hashCode ^= zobrist[HOROCK];
						break;
					case '.':
					case '!':
						zobrist = Arrays.copyOf(zobrist, 6);
						zobrist[STATIC] = random.nextLong();
						hashCode ^= zobrist[STATIC];
						break;
					default:
						if ('1' <= current && current <= '9')
						{
							targets.put(current, new Location(x, y));
							zobrist = Arrays.copyOf(zobrist, 6);
							zobrist[STATIC] = random.nextLong();
							hashCode ^= zobrist[STATIC];
						} else if ('A' <= current && current <= 'I')
						{
							trampolines[current - 'A'] = new Location(x, y);
							zobrist = Arrays.copyOf(zobrist, 6);
							zobrist[STATIC] = random.nextLong();
							hashCode ^= zobrist[STATIC];
						}
					}
					if(current == '*' || current == 'L' || current == 'W' || current == '@')
					{
						updatableCells.add(new Location(x, y));
					}
					GRIDSTRINGS[x][y] = zobrist;
				}
			}
			for (int x = row.length(); x < width; x++)
				grid[x][y] = ' '; // padding
		}
		OPENSTRING = random.nextLong();
		Collections.sort(updatableCells);

		water = 0;
		flooding = 0;
		waterproof = 10;
		trampolineTargets = new Location[9];
		growth = 25;
		razors = 0;
		if (raw.length > height)
		{
			for (int i = height + 1; i < raw.length; i++)
			{
				String[] metadata = raw[i].split(" ");
				String key = metadata[0];
				if (key.equals("Water"))
					water = Integer.parseInt(metadata[1]);
				else if (key.equals("Flooding"))
					flooding = Integer.parseInt(metadata[1]);
				else if (key.equals("Waterproof"))
					waterproof = Integer.parseInt(metadata[1]);
				else if (key.equals("Trampoline"))
					trampolineTargets[metadata[1].charAt(0) - 'A'] = targets.get(metadata[3].charAt(0));
				else if (key.equals("Growth"))
					growth = Integer.parseInt(metadata[1]);
				else if (key.equals("Razors"))
					razors = Integer.parseInt(metadata[1]);
			}
		}
		WATERSTRINGS = new long[height + 1];
		for(int i = 0; i <= height; i++)
		{
			WATERSTRINGS[i] = random.nextLong();
		}
		UNDERWATERSTRINGS = new long[waterproof + 2]; //0, 1-waterproof, waterproof+1; TECHNICALLY you don't need waterproof+1 but too lazy to improve on that atm -_-
		for(int i = 0; i <= waterproof + 1; i++)
		{
			UNDERWATERSTRINGS[i] = random.nextLong();
		}
		hashCode ^= WATERSTRINGS[water];
		hashCode ^= UNDERWATERSTRINGS[0];

		turnsUnderwater = 0;
		counter = 0;
	}

	public SearchGrid(SearchGrid grid) // deep copy
	{
		this.grid = new char[width][height];
		for (int i = 0; i < width; i++)
			System.arraycopy(grid.grid[i], 0, this.grid[i], 0, height);
		this.robo = grid.robo;
		this.water = grid.water;
		this.turnsUnderwater = grid.turnsUnderwater;
		this.razors = grid.razors;
		this.counter = grid.counter;
		this.updatableCells = new ArrayList<Location>(grid.updatableCells);
		this.nLambdas = grid.nLambdas;
		this.hashCode = grid.hashCode;
	}

	public Location getRobo()
	{
		return robo;
	}

	public SearchGrid update(Move move)
	{
		SearchGrid g = new SearchGrid(this);
		g.counter++;

		boolean changed = g.roboMove(move);

		Location robo = g.getRobo();
		boolean emptyAboveRobot = g.getChar(robo.getX(), robo.getY() + 1) == ' ';

		g.hashCode ^= UNDERWATERSTRINGS[g.turnsUnderwater]; //remove
		if (robo.getY() + 1 <= g.water)
		{
			g.turnsUnderwater++;
		} else
		{
			g.turnsUnderwater = 0;
		}
		g.hashCode ^= UNDERWATERSTRINGS[g.turnsUnderwater]; //and add

		changed = g.updateCells() || changed;

		//if the robot is dead or if there are no changes, don't consider this node
		//note that horocks become lambdas after crashing
		if ((emptyAboveRobot && (g.getChar(robo.getX(), robo.getY() + 1) == '*' || g.getChar(robo.getX(), robo.getY() + 1) == '\\')) || g.turnsUnderwater > waterproof ||
				!changed) //if the robot is dead or if there are no changes, don't consider this node
		{
			return null;
		}

		return g;
	}

	private boolean roboMove(Move move)
	{
		if (move == Move.WAIT)
			return false;
		if (move == Move.SHAVE) // evil beards
		{
			if (razors > 0)
			{
				razors--;
				int i = robo.getX(), j = robo.getY();
				boolean changed = false;
				if (getChar(i - 1, j) == 'W')
				{
					setChar(i - 1, j, ' ');
					updatableCells.remove(new Location(i - 1, j));
					changed = true;
				}
				if (getChar(i - 1, j + 1) == 'W')
				{
					setChar(i - 1, j + 1, ' ');
					updatableCells.remove(new Location(i - 1, j + 1));
					changed = true;
				}
				if (getChar(i, j + 1) == 'W')
				{
					setChar(i, j + 1, ' ');
					updatableCells.remove(new Location(i, j + 1));
					changed = true;
				}
				if (getChar(i + 1, j + 1) == 'W')
				{
					setChar(i + 1, j + 1, ' ');
					updatableCells.remove(new Location(i + 1, j + 1));
					changed = true;
				}
				if (getChar(i + 1, j) == 'W')
				{
					setChar(i + 1, j, ' ');
					updatableCells.remove(new Location(i + 1, j));
					changed = true;
				}
				if (getChar(i + 1, j - 1) == 'W')
				{
					setChar(i + 1, j - 1, ' ');
					updatableCells.remove(new Location(i + 1, j - 1));
					changed = true;
				}
				if (getChar(i, j - 1) == 'W')
				{
					setChar(i, j - 1, ' ');
					updatableCells.remove(new Location(i, j - 1));
					changed = true;
				}
				if (getChar(i - 1, j - 1) == 'W')
				{
					setChar(i - 1, j - 1, ' ');
					updatableCells.remove(new Location(i - 1, j - 1));
					changed = true;
				}
				return changed;
			}
			return false;
		}
		Location to = getDirectedLocation(robo, move);
		char toChar = getChar(to);
		// 2.2 condition 1
		if (toChar == ' ' || toChar == '.' || toChar == '\\' || toChar == 'O' || toChar == '!')
		{
			if (toChar == '\\')
			{
				nLambdas--;
				updatableCells.remove(to);
			} else if (toChar == '!')
			{
				razors++;
			}
		} else if ((toChar == '*' || toChar == '@') && (move == Move.LEFT || move == Move.RIGHT)) // 2.2 conditions 2 and 3
		{
			Location pushedPos = getDirectedLocation(to, move);
			if (getChar(pushedPos) == ' ')
			{
				setChar(pushedPos.getX(), pushedPos.getY(), toChar);
				updatableCells.remove(to);
				updatableCells.add(pushedPos);
				Collections.sort(updatableCells);
			} else
			{
				return false; // unsuccessful
			}
		} else if ('A' <= toChar && toChar <= 'I') // trampolines
		{
			to = trampolineTargets[toChar - 'A'];
			for (int i = 0; i < 9; i++)
			{
				Location target = trampolineTargets[i];
				if (target != null && target.equals(to)) //remove any trampoline whose target is this target
				{
					Location trampoline = trampolines[i];
					setChar(trampoline.getX(), trampoline.getY(), ' ');
				}
			}
		} else
		{
			return false; // unsuccessful
		}
		setChar(robo.getX(), robo.getY(), ' ');
		setChar(to.getX(), to.getY(), 'R');
		robo = to;
		return true;
	}

	private boolean updateCells()
	{
		char[][] newGrid = new char[width][height];
		for (int i = 0; i < width; i++)
			System.arraycopy(grid[i], 0, newGrid[i], 0, height);
		List<Location> toBeAdded = new ArrayList<Location>(), toBeRemoved = new ArrayList<Location>();
		for (Location location : updatableCells)
		{
			int i = location.getX(), j = location.getY();
			char curChar = getChar(i, j);
			if (curChar == '*' || curChar == '@')
			{
				char belowChar = getChar(i, j - 1);
				Location newLoc = null;
				if (belowChar == ' ')
				{
					setChar(newGrid, i, j, ' ');
					setChar(newGrid, i, j - 1, curChar);
					newLoc = new Location(i, j - 1);
				} else if (belowChar == '*' || belowChar == '@')
				{
					if (getChar(i + 1, j) == ' ' && getChar(i + 1, j - 1) == ' ')
					{
						setChar(newGrid, i, j, ' ');
						setChar(newGrid, i + 1, j - 1, curChar);
						newLoc = new Location(i + 1, j - 1);
					} else if (getChar(i - 1, j) == ' ' && getChar(i - 1, j - 1) == ' ')
					{
						setChar(newGrid, i, j, ' ');
						setChar(newGrid, i - 1, j - 1, curChar);
						newLoc = new Location(i - 1, j - 1);
					}
				} else if (belowChar == '\\' && getChar(i + 1, j) == ' ' && getChar(i + 1, j - 1) == ' ')
				{
					setChar(newGrid, i, j, ' ');
					setChar(newGrid, i + 1, j - 1, curChar);
					newLoc = new Location(i + 1, j - 1);
				}
				if (newLoc != null)
				{
					toBeRemoved.add(location);
					if (curChar == '@' && getChar(newLoc.getX(), newLoc.getY() - 1) != ' ')
					{
						setChar(newGrid, newLoc.getX(), newLoc.getY(), '\\');
					} else
					{
						toBeAdded.add(newLoc);
					}
				}
			} else if (curChar == 'L' && nLambdas == 0)
			{
				setChar(newGrid, i, j, 'O');
				hashCode ^= OPENSTRING;
				toBeRemoved.add(location);
			} else if (curChar == 'W' && growth != 0 && counter % growth == 0) // evil beards
			{
				if (getChar(i - 1, j) == ' ')
				{
					setChar(newGrid, i - 1, j, 'W');
					toBeAdded.add(new Location(i - 1, j));
				}
				if (getChar(i - 1, j + 1) == ' ')
				{
					setChar(newGrid, i - 1, j + 1, 'W');
					toBeAdded.add(new Location(i - 1, j + 1));
				}
				if (getChar(i, j + 1) == ' ')
				{
					setChar(newGrid, i, j + 1, 'W');
					toBeAdded.add(new Location(i, j + 1));
				}
				if (getChar(i + 1, j + 1) == ' ')
				{
					setChar(newGrid, i + 1, j + 1, 'W');
					toBeAdded.add(new Location(i + 1, j + 1));
				}
				if (getChar(i + 1, j) == ' ')
				{
					setChar(newGrid, i + 1, j, 'W');
					toBeAdded.add(new Location(i + 1, j));
				}
				if (getChar(i + 1, j - 1) == ' ')
				{
					setChar(newGrid, i + 1, j - 1, 'W');
					toBeAdded.add(new Location(i + 1, j - 1));
				}
				if (getChar(i, j - 1) == ' ')
				{
					setChar(newGrid, i, j - 1, 'W');
					toBeAdded.add(new Location(i, j - 1));
				}
				if (getChar(i - 1, j - 1) == ' ')
				{
					setChar(newGrid, i - 1, j - 1, 'W');
					toBeAdded.add(new Location(i - 1, j - 1));
				}
			}
		}
		grid = newGrid;

		boolean changed = false;
		if (toBeRemoved.size() > 0)
		{
			updatableCells.removeAll(toBeRemoved);
			changed = true;
		}
		if(toBeAdded.size() > 0)
		{
			updatableCells.addAll(toBeAdded);
			Collections.sort(updatableCells);
		}
		if (flooding != 0 && counter % flooding == 0)
		{
			hashCode ^= WATERSTRINGS[water]; //remove current water
			water = Math.min(water + 1, height);
			hashCode ^= WATERSTRINGS[water]; //add new after
			changed = true;
		}
		return changed;
	}

	private Location getDirectedLocation(Location o, Move move)
	{
		switch (move)
		{
		case UP:
			return new Location(o.getX(), o.getY() + 1);
		case DOWN:
			return new Location(o.getX(), o.getY() - 1);
		case LEFT:
			return new Location(o.getX() - 1, o.getY());
		case RIGHT:
			return new Location(o.getX() + 1, o.getY());
		default:
			return o;
		}
	}

	private char getChar(int x, int y)
	{
		if (0 <= x && x < width && 0 <= y && y < height)
		{
			return grid[x][y];
		}
		return '\0';
	}

	private char getChar(Location loc)
	{
		return getChar(loc.getX(), loc.getY());
	}

	private void setChar(int x, int y, char e)
	{
		setChar(grid, x, y, e);
	}

	private void setChar(char[][] grid, int x, int y, char e)
	{
		char current = grid[x][y];
		switch(current) //xor out the current char
		{
		case 'R':
			hashCode ^= GRIDSTRINGS[x][y][ROBOT]; break;
		case '*':
			hashCode ^= GRIDSTRINGS[x][y][ROCK]; break;
		case '\\':
			hashCode ^= GRIDSTRINGS[x][y][LAMBDA]; break;
		case 'W':
			hashCode ^= GRIDSTRINGS[x][y][BEARD]; break;
		case '@':
			hashCode ^= GRIDSTRINGS[x][y][HOROCK]; break;
		case '.':
		case '!':
			hashCode ^= GRIDSTRINGS[x][y][STATIC]; break;
		default:
			if (('1' <= current && current <= '9') || ('A' <= current && current <= 'I'))
			{
				hashCode ^= GRIDSTRINGS[x][y][STATIC];
			}
		}

		switch(e) //xor in the new char; static characters (. A-I 1-9 !) should not be able to be created
		{
		case 'R':
			hashCode ^= GRIDSTRINGS[x][y][ROBOT]; break;
		case '*':
			hashCode ^= GRIDSTRINGS[x][y][ROCK]; break;
		case '\\':
			hashCode ^= GRIDSTRINGS[x][y][LAMBDA]; break;
		case 'W':
			hashCode ^= GRIDSTRINGS[x][y][BEARD]; break;
		case '@':
			hashCode ^= GRIDSTRINGS[x][y][HOROCK]; break;
		}

		grid[x][y] = e;
	}

	@Override
	public String toString()
	{
		String output = "";
		output += '\n';
		for (int i = height - 1; i >= 0; i--)
		{
			for (int j = 0; j < width; j++)
			{
				output += grid[j][i];
			}
			if (i < water)
				output += "W\n";
			else
				output += "\n";
		}
		return output;
	}

	@Override
	public boolean equals(Object obj)
	{
		if (obj instanceof SearchGrid)
		{
			SearchGrid grid = (SearchGrid) obj;
			return Arrays.deepEquals(this.grid, grid.grid) && this.water == grid.water && this.turnsUnderwater == grid.turnsUnderwater;
		}
		return false;
	}

	@Override
	public int hashCode()
	{
		return (int) hashCode;
	}

	public long longHashCode()
	{
		return hashCode;
	}

}
